#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct stack
{
    int top;
    unsigned capacity;
    char *array;
} Stack;

// 创建指定容量的栈. 栈的大小初始化为0
Stack *createStack(unsigned capacity)
{
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    // 动态申请了 capacity 个 char 字节的地址空间
    stack->array = (char *)malloc(stack->capacity * sizeof(char));
    return stack;
}

// 栈顶 等于最后一个索引时堆栈已满
int isFull(Stack *stack)
{
    return stack->top == stack->capacity - 1;
}

// 栈顶索引等于-1时，表示空栈
int isEmpty(Stack *stack)
{
    return stack->top == -1;
}

int notEmpty(Stack *stack)
{
    return stack->top != -1;
}

// 进栈
void push(Stack *stack, int item)
{
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    printf("stack pushed>>%c \n", item);
}

// 出栈
int pop(Stack *stack)
{
    if (isEmpty(stack))
        exit(0);

    int value = stack->array[stack->top--];
    printf("stack poped>>%c \n", value);
    return value;
}

// 返回栈顶元素
int peek(Stack *stack)
{
    if (isEmpty(stack))
        exit(0);
    return stack->array[stack->top];
}

// ========================================

typedef struct queue
{
    char *array; // 队列元素
    int front;   // 队头位置
    int rear;    // 队尾位置
    int size;    // 队列的大小
} Queue;

// 创建队列
Queue *create(unsigned int size)
{
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->front = q->rear = 0; // 将队头和队尾都都置为0
    q->size = size;         // 初始化队列的大小
    // 动态申请数组的地址，size 个 char 字节的大小内存
    q->array = (char *)malloc(q->size * sizeof(char));

    return q;
}

int queueEmpty(Queue *q)
{
    return q->front == q->rear;
}

int queueFull(Queue *q)
{
    // 如果队尾位置+1 取队列长度 等于队头的位置则说明 队满
    return q->front == (q->rear + 1) % q->size;
}

void enqueue(Queue *q, char x)
{
    if (queueFull(q))
    {
        printf("the queue is full, can't be enqueue element\n");
        return;
    }

    q->array[q->rear] = x;
    q->rear = (q->rear + 1) % q->size;
    printf("enqueue value>>%c, front=%d, rear=%d\n", x, q->front, q->rear);
}

char dequeue(Queue *q)
{
    if (queueEmpty(q))
    {
        printf("the queue is empty, can't be dequeue element\n");
        return CHAR_MIN;
    }

    char x = q->array[q->front];
    // 获取队尾的位置
    q->front = (q->front + 1) % q->size;
    printf("dequeue value>>%c, front=%d, rear=%d\n", x, q->front, q->rear);
    return x;
}

char geFrontElement(Queue *q)
{
    if (queueEmpty(q))
    {
        printf("the queue is empty, can't be dequeue element\n");
        return CHAR_MIN;
    }

    return q->array[q->front];
}